//
// Created by pedro on 18-10-20.
//


#include "heap_sort.h"


int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * (i + 1);
}

void max_heapify(int *data, int index, int heap_size) {
    int l = left(index);
    int r = right(index);
    int largest;
    if (l < heap_size && data[l] > data[index]) {
        largest = l;
    } else {
        largest = index;
    }
    if (r < heap_size && data[r] > data[largest]) {
        largest = r;
    }

    if (largest != index) {
        swap(data, index, largest);
        max_heapify(data, largest, heap_size);
    }
}

void build_max_heap(int *data, int length) {
    // int length = sizeof(data) / sizeof(int);
    int heap_size = length;
    int len = (int) (length / 2) - 1;
    for (int i = len; i >= 0; i--) {
        max_heapify(data, i, heap_size);
    }
}

void heap_sort(int *data, int length) {
    build_max_heap(data, length);
    int len = length - 1;
    int heap_size = length;
    for (int i = len; i >= 1; i--) {
        swap(data, 0, i);
        heap_size -= 1;
        max_heapify(data, 0, heap_size);
    }
}

